This paper proposes graph linear notations and an extension of them with regular expressions. Graph linear notations are a set of strings to represent labeled general graphs. They are extended with regular expressions to represent sets of graphs by specifying chosen parts for selections and repetitions of certain induced subgraphs. Methods for the conversion between graph linear notations and labeled general graphs are shown. The NP-completeness of the membership problem for graph regular expressions is proved.

A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2n-1(n-1)!(n-3.5).

We characterized prion disease by comparing brain functional connectivity network (BFCN), which were constructed by 16-ch scalp-recorded electroencephalograms (EEGs). The connectivity between each pair of nodes (electrodes) were computed by synchronization likelihood (SL). The BFCN was applied to graph theory to discriminate prion disease patients from healthy elderlies and dementia groups.

Various graph algorithms have been developed with multiple random walks, the movement of several independent random walkers on a graph. Designing an efficient graph algorithm based on multiple random walks requires investigating multiple random walks theoretically to attain a deep understanding of their characteristics. The first meeting time is one of the important metrics for multiple random walks. The first meeting time on a graph is defined by the time it takes for multiple random walkers to meet at the same node in a graph. This time is closely related to the rendezvous problem, a fundamental problem in computer science. The first meeting time of multiple random walks has been analyzed previously, but many of these analyses focused on regular graphs. In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs and clarify the effects of graph structures on expected values. First, we derive the spectral formula of the expected first meeting time on the basis of spectral graph theory. Then, we examine the principal component of the expected first meeting time using the derived spectral formula. The clarified principal component reveals that (a) the expected first meeting time is almost dominated by $n/(1+d_{ m std}^2/d_{ mavg}^2)$ and (b) the expected first meeting time is independent of the starting nodes of random walkers, where n is the number of nodes of the graph. davg and dstd are the average and the standard deviation of weighted node degrees, respectively. Characteristic (a) is useful for understanding the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the variance of the coefficient dstd/davg (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

Spectral graph theory provides an algebraic approach to investigate the characteristics of weighted networks using the eigenvalues and eigenvectors of a matrix (e.g., normalized Laplacian matrix) that represents the structure of the network. However, it is difficult to accurately represent the structures of large-scale and complex networks (e.g., social network) as a matrix. This difficulty can be avoided if there is a universality, such that the eigenvalues are independent of the detailed structure in large-scale and complex network. In this paper, we clarify Wigner's Semicircle Law for weighted networks as such a universality. The law indicates that the eigenvalues of the normalized Laplacian matrix of weighted networks can be calculated from a few network statistics (the average degree, average link weight, and square average link weight) when the weighted networks satisfy a sufficient condition of the node degrees and the link weights.

The relationships between producers and consumers have changed radically by the recent growth of sharing economy. Promoting resource sharing can contribute to finding a solution to environmental issues (e.g. reducing food waste, consuming surplus electricity, and so on). Although prosumers have both roles as consumers and suppliers, matching between suppliers and consumers should be determined when the prosumers share resources. Especially, it is important to achieve envy-freeness that is a metric indicating how the number of prosumers feeling unfairness is kept small since the capacity of prosumers to supply resources is limited. Changing resource capacity and demand will make the situation more complex. This paper proposes a resource sharing model based on a temporal network and flows to realize envy-free resource sharing among prosumers. Experimental results demonstrate the deviation of envy among prosumers can be reduced by setting appropriate weights in a flow network.

Communication networks are now an essential infrastructure of society. Many services are constructed across multiple network domains. Therefore, the reliability of multi-domain networks should be evaluated to assess the sustainability of our society, but there is no known method for evaluating it. One reason is the high computation complexity; i.e., network reliability evaluation is known to be #P-complete, which has prevented the reliability evaluation of multi-domain networks. The other reason is intra-domain privacy; i.e., network providers never disclose the internal data required for reliability evaluation. This paper proposes a novel method that computes the lower and upper bounds of reliability in a distributed manner without requiring privacy disclosure. Our method is solidly based on graph theory, and is supported by a simple protocol that secures intra-domain privacy. Experiments on real datasets show that our method can successfully compute the reliability for 14-domain networks in one second. The reliability is bounded with reasonable errors; e.g., bound gaps are less than 0.1% for reliable networks.

Many countries have deregulated their electricity retail markets to offer lower electricity charges to consumers. However, many consumers have not switched their suppliers after the deregulation, and electricity suppliers do not tend to reduce their charges intensely. This paper proposes an electricity market model and evolutionary game to analyze the behavior of consumers in electricity retail markets. Our model focuses on switching costs such as an effort at switching, costs in searching for other alternatives, and so on. The evolutionary game examines whether consumers choose a strategy involving exploration of new alternatives with the searching costs as “cooperators” or not. Simulation results demonstrate that the share of cooperators was not improved by simply giving rewards for cooperators as compensation for searching costs. Furthermore, the results also suggest that the degree of cooperators in a network among consumers has a vital role in increasing the share of cooperators and switching rate.

Spectral graph theory, based on the adjacency matrix or the Laplacian matrix that represents the network topology and link weights, provides a useful approach for analyzing network structure. However, in large scale and complex social networks, since it is difficult to completely know the network topology and link weights, we cannot determine the components of these matrices directly. To solve this problem, we propose a method for indirectly determining the Laplacian matrix by estimating its eigenvalues and eigenvectors using the resonance of oscillation dynamics on networks.

Spectral graph theory gives an algebraic approach to the analysis of the dynamics of a network by using the matrix that represents the network structure. However, it is not easy for social networks to apply the spectral graph theory because the matrix elements cannot be given exactly to represent the structure of a social network. The matrix element should be set on the basis of the relationship between persons, but the relationship cannot be quantified accurately from obtainable data (e.g., call history and chat history). To get around this problem, we utilize the universality of random matrices with the feature of social networks. As such a random matrix, we use the normalized Laplacian matrix for a network where link weights are randomly given. In this paper, we first clarify that the universality (i.e., the Wigner semicircle law) of the normalized Laplacian matrix appears in the eigenvalue frequency distribution regardless of the link weight distribution. Then, we analyze the information propagation speed by using the spectral graph theory and the universality of the normalized Laplacian matrix. As a result, we show that the worst-case speed of the information propagation changes up to twice if the structure (i.e., relationship among people) of a social network changes.

The energy efficiency of Internet of Things (IoT) could be improved by RF energy transfer technologies.Aiming at IoT applications with a mobility-constrained mobile sink, a double-sourced energy transfer (D-ET) scheme is proposed. Based on the hierarchical routing information of network nodes, the Simultaneous Wireless Information and Power Transfer (SWIPT) method helps to improve the global data gathering performance. A genetic algorithm and graph theory are combined to analyze the node energy consumption distribution. Then dedicated charger nodes are deployed on the basis of the genetic algorithm's output. Experiments are conducted using Network Simulator-3 (NS-3) to evaluate the performance of the D-ET scheme. The simulation results show D-ET outperforms other schemes in terms of network lifetime and data gathering performance.

This paper proposes an oscillation model for analyzing the dynamics of activity propagation across social media networks. In order to analyze such dynamics, we generally need to model asymmetric interactions between nodes. In matrix-based network models, asymmetric interaction is frequently modeled by a directed graph expressed as an asymmetric matrix. Unfortunately, the dynamics of an asymmetric matrix-based model is difficult to analyze. This paper, first of all, discusses a symmetric matrix-based model that can describe some types of link asymmetry, and then proposes an oscillation model on networks. Next, the proposed oscillation model is generalized to arbitrary link asymmetry. We describe the outlines of four important research topics derived from the proposed oscillation model. First, we show that the oscillation energy of each node gives a generalized notion of node centrality. Second, we introduce a framework that uses resonance to estimate the natural frequency of networks. Natural frequency is important information for recognizing network structure. Third, by generalizing the oscillation model on directed networks, we create a dynamical model that can describe flaming on social media networks. Finally, we show the fundamental equation of oscillation on networks, which provides an important breakthrough for generalizing the spectral graph theory applicable to directed graphs.

Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.

This paper proposes a graph-theory-based Euler number computing algorithm. According to the graph theory and the analysis of a mask's configuration, the Euler number of a binary image in our algorithm is calculated by counting four patterns of the mask. Unlike most conventional Euler number computing algorithms, we do not need to do any processing of the background pixels. Experimental results demonstrated that our algorithm is much more efficient than conventional Euler number computing algorithms.

Wireless sensor networks (WSNs) consist of numerous wireless sensor nodes, each sensor node embedding a tiny communication device enabling the nodes to communicate with each other or the base station. In this paper, we investigate the problem that communication distance must be considered in minimizing the wireless communication energy since the energy consumption is proportional to the 2nd to the 6th power of the distance. Moreover, another problem is that there is a non-uniform energy drain effect in most topologies. Known as the energy hole problem, it can result in premature termination of the entire network. To address these problems, in this paper we first propose a communication routing algorithm that can solve the energy hole problem to the maximum extent possible while minimizing the wireless communication energy by generating an energy efficient spanning tree. This algorithm is beneficial for network lifetimes defined by a high node termination percentage. For the WSNs for which the energy hole problem is critical, we propose two route switching algorithms to solve the energy hole problem; they are beneficial for network lifetimes defined by a low node termination percentage. Simulation results showed that these algorithms avoid the energy hole problem and thereby greatly extend the lifetime of WSNs by more than 3 to 6 times that of ones using direct transmission in a 20-node network and a 50-node network if the lifetime of a WSN is defined by 1% of the number of terminated nodes in the WSN.

We present a recovery scheme based on Self-protected Spanning Tree (SST), which recovers from failure all by itself. In the recovery scheme, the links are assigned birthdays to denote the order in which they are to be considered for adding to the SST. The recovery mechanism, named Birthday-based Link Replacing Mechanism (BLRM), is able to transform a SST into a new spanning tree by replacing some tree links with some non-tree links of the same birthday, which ensures the network connectivity after any single link or node failure. First, we theoretically prove that the SST-based recovery scheme can be applied to arbitrary two-edge connected or two connected networks. Then, the recovery time of BLRM is analyzed and evaluated using Ethernet, and the simulation results demonstrate the effectiveness of BLRM in achieving fast recovery. Also, we point out that BLRM provides a novel load balancing mechanism by fast changing the topology of the SST.

This paper deals with a strategic issue in the stable marriage model with complete preference lists (i.e., a preference list of an agent is a permutation of all the members of the opposite sex). Given complete preference lists of n men over n women, and a marriage µ, we consider the problem for finding preference lists of n women over n men such that the men-proposing deferred acceptance algorithm (Gale-Shapley algorithm) adopted to the lists produces µ. We show a simple necessary and sufficient condition for the existence of a set of preference lists of women over men. Our condition directly gives an O(n2) time algorithm for finding a set of preference lists, if it exists.

A consensus problem has been studied in many fundamental and application fields to analyze coordinated behavior in multi-agent systems. In a consensus problem, it is usually assumed that a state of each agent is scalar and all agents have an identical linear consensus protocol. We present a consensus problem of multi-agent systems where each agent has multiple state variables and a performance value evaluated by a nonlinear performance function according to its current state. We derive sufficient conditions for agents to achieve consensus on the performance value using an algebraic graph theory and the mean value theorem. We also consider an application of a performance consensus problem to resource allocation in soft real-time systems so as to achieve a fair QoS (Quality of Service) level.

This paper addresses a discrete-time consensus problem with non-linear performance functions over dynamically changing communication topologies. Each agent has a performance value based on its internal information state and exchanges the performance value with other agents to achieve consensus. We derive sufficient conditions for a global consensus using algebraic graph theory.

Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):(1) G is a directed graph with two disjoint vertex sets A and B. (2) There are r11 (r22, respectively) directed edges between every pair of vertices in A(B), and r12 directed edges between every pair of vertex in A and vertex in B. Then G is called an (r11, r12, r22)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.